package main.Q1101_1200;

import java.util.*;

public class Q1161_1170 {
    public static void main(String[] args) {
        System.out.println("Question1161：最大层内元素和");
        System.out.println("Question1162：地图分析");
        System.out.println("Question1163：");
        System.out.println("Question1164：");
        System.out.println("Question1165：");
        System.out.println("Question1166：");
        System.out.println("Question1167：");
        System.out.println("Question1168：");
        System.out.println("Question1169：");
        System.out.println("Question1170：");
    }
}

class Question1161 {
    public int maxLevelSum(TreeNode root) {
        int result = 1, maxSum = root.val, curLevel = 1, curCounts = 1, nextCounts = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int curSum = 0;
            for (int i = 0; i < curCounts; i++) {
                TreeNode curNode = queue.poll();
                curSum += curNode.val;
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                    nextCounts++;
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                    nextCounts++;
                }
            }
            if (curSum > maxSum) {
                result = curLevel;
                maxSum = curSum;
            }
            curLevel++;
            curCounts = nextCounts;
            nextCounts = 0;
        }
        return result;
    }
}

class Question1162 {
    public int maxDistance(int[][] grid) {
        final int INF = 1000000;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int n = grid.length;
        int[][] d = new int[n][n];
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] status1, int[] status2) {
                return status1[0] - status2[0];
            }
        });

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = INF;
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    d[i][j] = 0;
                    queue.offer(new int[]{0, i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] f = queue.poll();
            for (int i = 0; i < 4; ++i) {
                int nx = f[1] + dx[i], ny = f[2] + dy[i];
                if (!(nx >= 0 && nx < n && ny >= 0 && ny < n)) {
                    continue;
                }
                if (f[0] + 1 < d[nx][ny]) {
                    d[nx][ny] = f[0] + 1;
                    queue.offer(new int[]{d[nx][ny], nx, ny});
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ans = Math.max(ans, d[i][j]);
                }
            }
        }

        return ans == INF ? -1 : ans;
    }
}